home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 236_01 / bawkpat.c < prev    next >
Text File  |  1989-06-05  |  8KB  |  365 lines
  1. /*
  2.     HEADER:        CUG236;
  3.     TITLE:        BAWK Regular Expression Interpreter;
  4.     DATE:        05/17/1987;
  5.     VERSION:    1.1;
  6.     FILENAME:    BAWKPAT.C;
  7.     SEE-ALSO:    BAWK.C;
  8.     AUTHORS:    W. C. Colley III, B. Brodt;
  9. */
  10.  
  11. /*
  12.  * Bawk regular expression compiler/interpreter
  13.  */
  14. #include <stdio.h>
  15. #include "bawk.h"
  16.  
  17. /* Functions local to this module.    */
  18.  
  19. char *cclass(), *pmatch();
  20.  
  21. int re_compile( patbuf )
  22. char    *patbuf;        /* where to put compiled pattern */
  23. {
  24.     /*
  25.      * Compile a regular expression from current input file
  26.      * into the given pattern buffer.
  27.      */
  28.     int    c,        /* Current character         */
  29.         o;        /* Temp                 */
  30.     char    *patptr,    /* destination string pntr   */
  31.         *lp,        /* Last pattern pointer         */
  32.         *spp,        /* Save beginning of pattern */
  33.         delim;        /* pattern delimiter         */
  34.  
  35.     patptr = patbuf;
  36.     delim = getcharacter();
  37.  
  38.     while ( (c = getcharacter()) != -1 && c != delim )
  39.     {
  40.         /*
  41.          * STAR, PLUS and MINUS are special.
  42.          */
  43.         if (c == '*' || c == '+' || c == '-') {
  44.             if (patptr == patbuf ||
  45.                   (o=patptr[-1]) == BOL ||
  46.                   o == EOL ||
  47.                   o == STAR ||
  48.                   o == PLUS ||
  49.                   o == MINUS)
  50.                 error( "illegal occurrance op", RE_ERROR );
  51.             *patptr++ = ENDPAT;
  52.             *patptr++ = ENDPAT;
  53.             spp = patptr;        /* Save pattern end    */
  54.             while (--patptr > lp)    /* Move pattern down... */
  55.                 *patptr = patptr[-1];    /* one byte    */
  56.             *patptr =   (c == '*') ? STAR :
  57.                 (c == '-') ? MINUS : PLUS;
  58.             patptr = spp;        /* Restore pattern end    */
  59.             continue;
  60.         }
  61.         /*
  62.          * All the rest.
  63.          */
  64.         lp = patptr;            /* Remember start    */
  65.         switch(c) {
  66.  
  67.         case '^':
  68.             *patptr++ = BOL;
  69.             break;
  70.  
  71.         case '$':
  72.             *patptr++ = EOL;
  73.             break;
  74.  
  75.         case '.':
  76.             *patptr++ = ANY;
  77.             break;
  78.  
  79.         case '[':
  80.             patptr = cclass( patptr );
  81.             break;
  82.  
  83.         case ':':
  84.             if ( (c=getcharacter()) != -1 )
  85.             {
  86.                 switch( tolower( c ) )
  87.                 {
  88.  
  89.                 case 'a':
  90.                     *patptr++ = ALPHA;
  91.                     break;
  92.  
  93.                 case 'd':
  94.                     *patptr++ = DIGIT;
  95.                     break;
  96.  
  97.                 case 'n':
  98.                     *patptr++ = NALPHA;
  99.                     break;
  100.  
  101.                 case ' ':
  102.                     *patptr++ = PUNCT;
  103.                     break;
  104.  
  105.                 default:
  106.                     error( "unknown ':' type", RE_ERROR );
  107.  
  108.                 }
  109.             }
  110.             else
  111.                 error( "no ':' type", RE_ERROR );
  112.             break;
  113.  
  114.         case '\\':
  115.             c = getcharacter();
  116.  
  117.         default:
  118.             *patptr++ = CHAR;
  119.             *patptr++ = c;
  120.         }
  121.     }
  122.     *patptr++ = ENDPAT;
  123.     *patptr++ = 0;            /* Terminate string    */
  124.  
  125. #ifdef DEBUG
  126.     if ( Debug>1 )
  127.     {
  128.         for ( lp=patbuf; lp<patptr; ++lp )
  129.         {
  130.             switch ( c = *lp )
  131.             {
  132.             case CHAR:    printf("char "); break;
  133.             case BOL:    printf("bol "); break;
  134.             case EOL:    printf("eol "); break;
  135.             case ANY:    printf("any "); break;
  136.             case CLASS:    printf("class(%d) ", *++lp); break;
  137.             case NCLASS:    printf("notclass(%d) ",*++lp); break;
  138.             case STAR:    printf("star "); break;
  139.             case PLUS:    printf("plus "); break;
  140.             case MINUS:    printf("minus "); break;
  141.             case ALPHA:    printf("alpha "); break;
  142.             case DIGIT:    printf("digit "); break;
  143.             case NALPHA:    printf("notalpha "); break;
  144.             case PUNCT:    printf("punct "); break;
  145.             case RANGE:    printf("range "); break;
  146.             case ENDPAT:    printf("endpat "); break;
  147.             default:    printf("<%c> ", c); break;
  148.             }
  149.         }
  150.         printf( "\n" );
  151.     }
  152. #endif
  153.  
  154.     return patptr - patbuf;
  155. }
  156.  
  157. char *cclass( patbuf )
  158. char    *patbuf;    /* destination pattern buffer */
  159. {
  160.     /*
  161.      * Compile a class (within [])
  162.      */
  163.     char    *patptr,    /* destination pattern pointer */
  164.         *cp;        /* Pattern start     */
  165.     int    c,        /* Current character */
  166.         o;        /* Temp             */
  167.  
  168.     patptr = patbuf;
  169.  
  170.     if ( (c = getcharacter()) == -1 )
  171.         error( "class terminates badly", RE_ERROR );
  172.     else if ( c == '^')
  173.     {
  174.         /*
  175.          * Class exclusion, for example: [^abc]
  176.          * Swallow the "^" and set token type to class exclusion.
  177.          */
  178.         o = NCLASS;
  179.     }
  180.     else
  181.     {
  182.         /*
  183.          * Normal class, for example: [abc]
  184.          * push back the character and set token type to class
  185.          */
  186.         ungetcharacter( c );
  187.         o = CLASS;
  188.     }
  189.     *patptr++ = o;
  190.  
  191.     cp = patptr;    /* remember where byte count is */
  192.     *patptr++ = 0;    /* and initialize byte count */
  193.     while ( (c = getcharacter()) != -1 && c!=']' )
  194.     {
  195.         o = getcharacter();        /* peek at next char */
  196.         if (c == '\\')            /* Store quoted chars */
  197.         {
  198.             if ( o == -1) /* Gotta get something */
  199.                 error( "class terminates badly", RE_ERROR );
  200.             *patptr++ = o;
  201.         }
  202.         else if ( c=='-' && (patptr-cp)>1 && o!=']' && o != -1 )
  203.         {
  204.             c = patptr[-1];        /* Range start       */
  205.             patptr[-1] = RANGE;    /* Range signal       */
  206.             *patptr++ = c;        /* Re-store start  */
  207.             *patptr++ = o;        /* Store end char  */
  208.         }
  209.         else
  210.         {
  211.             *patptr++ = c;        /* Store normal char */
  212.             ungetcharacter( o );
  213.         }
  214.     }
  215.     if (c != ']')
  216.         error( "unterminated class", RE_ERROR );
  217.     if ( (c = (patptr - cp)) >= 256 )
  218.         error( "class too large", RE_ERROR );
  219.     if ( c == 0 )
  220.         error( "empty class", RE_ERROR );
  221.     *cp = c;        /* fill in byte count */
  222.  
  223.     return patptr;
  224. }
  225.  
  226. int match( line, pattern )
  227. char    *line;        /* line to match */
  228. char    *pattern;    /* pattern to match */
  229. {
  230.     /*
  231.      * Match the current line (in Linebuf[]), return 1 if it does.
  232.      */
  233.     char    *l;        /* Line pointer          */
  234.     char    *next;
  235.     int    matches;
  236.  
  237.     matches = 0;
  238.     for (l = line; *l; l++)
  239.     {
  240.         if ( next = pmatch(line, l, pattern) )
  241.         {
  242.             l = next - 1;
  243.             ++matches;
  244. #ifdef DEBUG
  245.             if ( Debug )
  246.                 printf( "match!\n" );
  247. #endif
  248.         }
  249.     }
  250.  
  251.     return matches;
  252. }
  253.  
  254. char *pmatch(linestart, line, pattern)
  255. char    *linestart;    /* start of line to match */
  256. char    *line;        /* (partial) line to match    */
  257. char    *pattern;    /* (partial) pattern to match    */
  258. {
  259.     char    *l;    /* Current line pointer        */
  260.     char    *p;    /* Current pattern pointer    */
  261.     char    c;    /* Current character        */
  262.     char    *e;    /* End for STAR and PLUS match    */
  263.     int    op;    /* Pattern operation        */
  264.     int    n;    /* Class counter        */
  265.     char    *are;    /* Start of STAR match        */
  266.  
  267.     l = line;
  268.  
  269. #ifdef DEBUG
  270.     if (Debug > 1)
  271.         printf("pmatch(\"%s\")\n", line);
  272. #endif
  273.  
  274.     p = pattern;
  275.     while ((op = *p++) != ENDPAT) {
  276.  
  277. #ifdef DEBUG
  278.         if (Debug > 1)
  279.             printf("byte[%d] = 0%o, '%c', op = 0%o\n",
  280.                     l-line, *l, *l, op);
  281. #endif
  282.  
  283.         switch(op) {
  284.  
  285.         case CHAR:
  286.             if ( *l++ != *p++) return NULL;
  287.             break;
  288.  
  289.         case BOL:
  290.             if (l != linestart) return NULL;
  291.             break;
  292.  
  293.         case EOL:
  294.             if (*l) return NULL;
  295.             break;
  296.  
  297.         case ANY:
  298.             if (!*l++) return NULL;
  299.             break;
  300.  
  301.         case DIGIT:
  302.             c = *l++;
  303.             if (!isdigit(c)) return NULL;
  304.             break;
  305.  
  306.         case ALPHA:
  307.             c = *l++;
  308.             if (!isalpha(c)) return NULL;
  309.             break;
  310.  
  311.         case NALPHA:
  312.             c = *l++;
  313.             if (!isalnum(c)) return NULL;
  314.             break;
  315.  
  316.         case PUNCT:
  317.             if (!(c = *l++) || c > ' ') return NULL;
  318.             break;
  319.  
  320.         case CLASS:
  321.         case NCLASS:
  322.             c = *l++;
  323.             n = *p++ & 0377;
  324.             do {
  325.                 if (*p == RANGE) {
  326.                     p += 3;
  327.                     n -= 2;
  328.                     if (c >= p[-2] && c <= p[-1])
  329.                         break;
  330.                 }
  331.                 else if (c == *p++)
  332.                     break;
  333.             } while (--n > 1);
  334.             if ((op == CLASS) == (n <= 1)) return NULL;
  335.             if (op == CLASS) p += n - 2;
  336.             break;
  337.  
  338.         case MINUS:
  339.             e = pmatch(linestart,l,p);/* Look for a match     */
  340.             while (*p++ != ENDPAT); /* Skip over pattern   */
  341.             if (e)            /* Got a match?           */
  342.                 l = e;        /* Yes, update string  */
  343.             break;            /* Always succeeds     */
  344.  
  345.         case PLUS:            /* One or more ...     */
  346.             if (!(l = pmatch(linestart,l,p))) return NULL;
  347.                         /* Gotta have a match  */
  348.         case STAR:            /* Zero or more ...    */
  349.             for (are=l; *l && (e = pmatch(linestart,l,p)); l=e);
  350.                         /* Get longest match   */
  351.             while (*p++ != ENDPAT); /* Skip over pattern   */
  352.             do {            /* Try to match rest   */
  353.                 if (e = pmatch(linestart,l,p))
  354.                     return e;
  355.             } while (l-- > are);
  356.             return NULL;        /* Nothing else worked */
  357.  
  358.         default:
  359.             fprintf( stderr, "bad op code %d\n", op );
  360.             error( "can't happen -- match", RE_ERROR );
  361.         }
  362.     }
  363.     return l;
  364. }
  365.